//94. 二叉树的中序遍历
//思路：1.先求出二叉树的节点个数
//2.再开辟动态内存
//3.最后中序遍历，将数据存放到开的内存中

// C语言版本
//#include <stdlib.h>
//struct TreeNode {
//	int val;
//	struct TreeNode* left;
//	struct TreeNode* right;
//};
//int TreeSize(struct TreeNode* root)
//{
//	if (NULL == root)
//		return 0;
//
//	return TreeNode(root->left)
//		+ TreeNode(root->right) + 1;
//}
//void _inorder(struct TreeNode* root, int* a, int* pi)
//{
//	if (NULL == root)
//		return;
//
//	_inorder(root->left, a, pi);
//	a[(*pi)++] = root->val;
//	_inorder(root->right, a, pi);
//}
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//	*returnSize = TreeSize(root);
//	int* a = (int*)malloc(*returnSize * sizeof(int));
//	int i = 0;
//
//	_inorder(root, a, &i);
//	return a;
//}


// C++非递归版本
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
	vector<int> inorderTraversal(TreeNode* root)
	{
		stack<TreeNode*> st;
		vector<int> ret;
		TreeNode* cur = root;

		while (cur || !st.empty())
		{
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			TreeNode* top = st.top();
			ret.push_back(top->val);
			cur = top->right;
		}
		return ret;
	}
};